// 由题可知，所有数字会被分成正数和负数两部分
// 设正数的和为a，负数绝对值的和为b
// 则：a + b = sum, a - b = target
// 则：a = (sum + target) / 2
// 即题目转换为了 在数组中选数，和为a的选法——01背包


// 空间优化
class Solution {
public:
    int findTargetSumWays(vector<int>& nums, int target) {
        int sum = 0;
        for (auto& i : nums)
            sum += i;
        
        int v = (sum + target) / 2, n = nums.size();
        if ((sum + target) % 2 || v < 0)
            return 0;

        vector<int> dp(v + 1, 0);
        dp[0] = 1;

        for (int i = 1; i < n + 1; i++)
            for (int j = v; j >= nums[i - 1]; j--)
                dp[j] += + dp[j - nums[i - 1]];

        return dp[v];
    }
};

// //dp[i][j]表示：考虑前i个元素，当和等于j时，有多少种选法
// class Solution {
// public:
//     int findTargetSumWays(vector<int>& nums, int target) {
//         int sum = 0;
//         for (auto& i : nums)
//             sum += i;
        
//         int v = (sum + target) / 2, n = nums.size();
//         if ((sum + target) % 2 || v < 0)
//             return 0;

//         vector<vector<int>> dp(n + 1, vector<int>(v + 1, 0));
//         dp[0][0] = 1;

//         for (int i = 1; i < n + 1; i++)
//         {
//             for (int j = 0; j < v + 1; j++)
//             {
//                 dp[i][j] = dp[i - 1][j] + ((j - nums[i - 1]) >= 0 ? dp[i - 1][j - nums[i - 1]] : 0);
//             }
//         }

//         return dp[n][v];
//     }
// };

// //回溯
// class Solution {
// private:
//     void dfs(vector<int>& nums, int pos)
//     {
//         if (pos == nums.size())
//         {
//             if ( _path == _target)
//                 _ret++;
//             return;
//         }

//         _path += nums[pos];
//         dfs(nums, pos + 1);
//         _path -= nums[pos];

//         _path -= nums[pos];
//         dfs(nums, pos + 1);
//         _path += nums[pos];
//     }
// public:
//     int findTargetSumWays(vector<int>& nums, int target) {
//         _target = target;
//         dfs(nums, 0);

//         return _ret;
//     }
// private:
//     int _ret = 0;
//     int _target;
//     int _path = 0;
// };